package training_camp.day2.leetcode76;

import java.util.HashMap;
import java.util.Set;

class Solution {
    public String minWindow(String s, String t) {
        HashMap<Character, Integer> sMap = new HashMap<>();
        HashMap<Character, Integer> tMap = new HashMap<>();
        char[] chars = t.toCharArray();
        for (char c : chars) {
            tMap.put(c, tMap.getOrDefault(c, 0) + 1);
        }
        int left = 0;
        int right = 0;
        int leftIndex = -1;
        int rightIndex = -1;
        char[] array = s.toCharArray();
        int n = array.length;
        int minLength = Integer.MAX_VALUE;
        while (right < n) {
            sMap.put(array[right], sMap.getOrDefault(array[right], 0) + 1);
            while (check(sMap, tMap)) {
                sMap.put(array[left], sMap.get(array[left]) - 1);
                if (right - left + 1 < minLength) {
                    leftIndex = left;
                    rightIndex = right;
                    minLength = rightIndex -leftIndex+1;
                }
                left++;
            }
            right++;
        }
        return rightIndex == -1 && leftIndex == -1 ? "" : s.substring(leftIndex, rightIndex + 1);

    }

    boolean check(HashMap<Character, Integer> sMap, HashMap<Character, Integer> tMap) {
        Set<Character> set = tMap.keySet();
        for (Character c : set) {
            if (!sMap.containsKey(c)) {
                return false;
            }
            if (sMap.get(c) < tMap.get(c)) {
                return false;
            }
        }
        return true;
    }
}